package com.gxc.rapacity;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入:
 正数数组costs
 正数数组profits
 正k
 正m
 含义:
 costs[i]表示i号项目的花费
 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 k表示你只能串行的最多做k个项目
 m表示你初始的资金
 说明:
 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目
 输出:
 你最后获得的最大钱数
 */
public class MaximumBenefit {
    
    public static void main(String[] args) {
        int[] costs = {3,1,4,9,9};
        int[] profits = {1,2,3,7,4};
        int k = 4;
        int m = 3;
        Project[] items = new Project[5];
        items[0] = new Project(3,1);
        items[1] = new Project(1,2);
        items[2] = new Project(4,3);
        items[3] = new Project(9,7);
        items[4] = new Project(9,4);
        int max = maximumBenefit(items, k, m);
        System.out.println(max);

        max = maximumBenefit2(costs, profits, k, m);
    }

    private static int maximumBenefit2(int[] costs, int[] profits, int k, int m) {
        //花费的小跟堆
        PriorityQueue<Project> costsQueue = new PriorityQueue(new CostComparator());
        for (int i = 0; i < costs.length; i++) {
            costsQueue.add(new Project(costs[i], profits[i]));
        }
        //利润的大跟堆
        PriorityQueue<Project> profitsQueue = new PriorityQueue(new ProfitsComparator());

        //最多K个项目
        for (int i = 0; i < k; i++) {
            //花费小于资金的项目根据利润大小进入大跟堆
            while (!costsQueue.isEmpty() && costsQueue.peek().cost<=m) {
                profitsQueue.add(costsQueue.poll());
            }
            if (profitsQueue.isEmpty()) {
                return m;
            }
            m+=profitsQueue.poll().profit;
        }
        return m;
    }

    private static int maximumBenefit(Project[] item, int k, int m) {
        //花费的小跟堆
        PriorityQueue<Project> costsQueue = new PriorityQueue(new CostComparator());
        for (Project cost : item) {
            costsQueue.add(cost);
        }
        //利润的大跟堆
        PriorityQueue<Project> profitsQueue = new PriorityQueue(new ProfitsComparator());

        int sum = m;
        //最多K个项目
        for (int i = 0; i < k; i++) {
            //花费小于资金的项目根据利润大小进入大跟堆
            while (!costsQueue.isEmpty() && costsQueue.peek().cost<=sum) {
                profitsQueue.add(costsQueue.poll());
            }
            if (!profitsQueue.isEmpty()) {
                sum+=profitsQueue.poll().profit;
            }
        }
        return sum;
    }

    public static class CostComparator implements Comparator<Project> {
        @Override
        public int compare(Project o1, Project o2) {
            return o1.cost-o2.cost;
        }
    }

    public static class ProfitsComparator implements Comparator<Project> {
        @Override
        public int compare(Project o1, Project o2) {
            return o2.profit-o1.profit;
        }
    }

    public static class Project {
        public int cost;
        public int profit;

        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }
}
